package com.xhh.learning.record.algorithm;

/**
 * 类名： QueensOf8
 * 描述： 八皇后
 * 作者： Administrator
 * 版本： V1.0
 * 创建时间:  2019/5/21 14:50
 * 最后修改时间:  2019/5/21 14:50
 */
public class QueensOf8 {

    public static void main(String[] args) {
        cal8queens(new int[4], 0);
    }

    private static void cal8queens(int[] a, int row) {

        if (row >= a.length) {
            print(a);
            return;
        }

        for (int col = 0; col < a.length; col++) {
            if (isOk(a, row, col)) {
                a[row] = col;
                cal8queens(a, row+1);
            }
        }
    }

    private static boolean isOk(int[] a, int row, int col) {
        int leftUp = col - 1;
        int rightUp = col + 1;
        for (int i = row - 1; i >= 0; i--) {

            if (a[i] == col) {
                return false;
            }

            if (leftUp >= 0 && a[i] == leftUp) {
                return false;
            }

            if (rightUp < a.length && a[i] == rightUp) {
                return false;
            }
            leftUp--;
            rightUp++;
        }
        return true;
    }

    private static void print(int[] a) {
        for (int col : a) {
            for (int j = 0; j < a.length; j++) {
                if (j == col) {
                    System.out.print("Q ");
                } else {
                    System.out.print("+ ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}
